package baseclass.e_tree;


/**
    判断一颗树是否是平衡二叉树：
    平衡二叉树概念：左子树平衡，右子树平衡，且左右子树的高度差不大于1
    所以遍历树的所有节点，每次到一个节点，就判断一次是否是平衡二叉树
 */
public class Code06_IsBalanceTree {

     static class ReturnData{
        private boolean isBalance;
        private int height;
        ReturnData(boolean isBalance, int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }

    public static boolean isBalance(Node head){
        return process(head).isBalance;
    }
    private static ReturnData process(Node head){
        if(head == null){
            //空节点 ，是BT，高度为0
            return new ReturnData(true,0);
        }

        ReturnData leftData = process(head.left);
        //判断左子树是否平衡
        if(!leftData.isBalance)
            return new ReturnData(false,-1);

        ReturnData rightDate = process(head.right);
        //判断右子树是否平衡
        if(!rightDate.isBalance)
            return new ReturnData(false,-1);

        //否则当前数是否平衡
        if(Math.abs(leftData.height - rightDate.height) > 1){
            return new ReturnData(false,-1);
        }
        //上面不成立则是平衡，当前数的高度等于左右子树高度的max + 1
        return new ReturnData(true,Math.max(leftData.height,rightDate.height) + 1);
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        head.right.right.right = new Node(7);
//        head.right.right.right.right = new Node(7);

        System.out.println(isBalance(head));


        Long a = 1L;
        Integer b = 2;
        System.out.println(a < b);

    }
}
